package org.example.myleet.p1619;

import java.util.Arrays;

public class Solution {
//    public double trimMean(int[] arr) {
//        int n = arr.length;
//        Arrays.sort(arr);
//        int fivePercent = (int) ((double) n * 0.05);
//        int sum = 0, count = 0;
//        for (int i = fivePercent; i < n - fivePercent; ++i) {
//            sum += arr[i];
//            ++count;
//        }
//        double res = (double) sum / (double) count;
//        String s = String.format("%.5f", res);
//        res = Double.parseDouble(s);
//        return res;
//    }

    public double trimMean(int[] arr) {
        int n = arr.length;
        int fivePercent = (int) ((double) n * 0.05);
        int end = n - fivePercent;
        int sum = 0, sumCount = 0;
        //桶排序
        int max = 0;
        for (int number : arr) {
            max = Math.max(max, number);
        }
        int[] buckets = new int[max + 1];
        for (int number : arr) {
            ++buckets[number];
        }
        int i = 0;
        for (int number = 0; number <= max; ++number) {
            int count = buckets[number];
            if (count > 0) {
                for (int j = 0; j < count; ++j) {
                    if (fivePercent <= i) {
                        if (i >= end) break;
                        sum += number;
                        ++sumCount;
                    }
                    i++;
                }
            }
        }
        double res = (double) sum / (double) sumCount;
//        String s = String.format("%.5f", res);
//        res = Double.parseDouble(s);
        return res;
    }
}
